МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ ІНСТРУКЦІЯ до лабораторної роботи № 2 з курсу “ Основи збору, передачі та обробки інформації” для студентів базового напряму 6.1601 “Захист інформації” Затверджено на засiданнi кафедри "Захист інформації" Протокол N вiд . .2007 p. Львів 2007 Дослідження кодоутворення та принципів побудови кодерів і декодерів циклічних кодів: інструкція до лабораторної роботи № 2 з курсів «Основи збору, передачі та обробки інформації» для студентів базового напрямку «Захист інформації» усіх форм навчання / Укл. М. В. Кіріанакі, В. В. Хома, В. І. Отенко, Я. Р. Совин. - Львів: НУЛП, 2007. - 9 с. Укладачі: М. В. Кіріанакі, канд. техн. наук, доц., В. В. Хома, док. техн. наук, проф., В. І. Отенко, канд. техн. наук, доц., Я. Р. Совин, асист. Відповідальний за випуск М. В.Кіріанакі, канд. техн. наук., доц. Рецензенти: З. Р. Мичуда, канд. техн. наук., доц. О. В. Івахів, канд. техн. наук.. доп. Складання і відлагодження схеми здійснено асист. каф. захисту інформації Совином Я. Р. Мета роботи – ознайомлення з основами кодування і декодування цифрової інформації циклічними кодами і набуттю практичних навиків розробки функціональних схем кодерів і декодерів. 1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ Циклічні коди (ЦК) є одними з найпростіших в реалізації та ефективних у забезпеченні високої завадостійкості і завдяки цьому широко використовуються не лише в телемеханіці, але і в обчислювальній техніці та зв’язку. Для утворення циклічних кодів використовуються так звані неприведені поліноми Р(х), тобто многочлени, які не можна представити добутком поліномів нижчих степенів. Існує декілька різних способів кодування [1, 2]. Найпростіший спосіб утворення ЦК полягає у множенні многочлена G(х)1, який відповідає інформаційним ni розрядам первинного (безнадлишкового) коду, на утворюючий поліном Р(х). Такий спосіб легко реалізувати, але йому притаманний суттєвий недолік: одержані в результаті множення комбінації ЦК не містять в явному вигляд інформаційні розряди. Після виправлення помилок такі комбінації для виділення інформаційних символів доводиться ділити на утворюючий поліном. Інший спосіб передбачає відведення під інформаційні ni , символи старших розрядів коду, а під контрольні nk = n - ni, символів молодших розрядів. Для утворення ЦК використовується така процедура. Многочлен G(х) який відповідає ni - розрядній кодовій комбінації (КК) первинного коду, множиться на
. Ця операція еквівалентна приписуванню із боку молодших розрядів G(х) - nk нулів. Добуток G(х)*
ділиться на утворюючий поліном Р(х). При цьому одержують частку Q(x) того ж степеня, що і G(х), та залишок R(x), який додається до G(х)*
. Отже, КК циклічного коду буде визначатися як поліном F(x) = G(х)*
( R(х) (1) Оскільки степінь Р(х) вибирають nk, степінь залишку R(х), не перевищує nk - 1. В комбінації, що відповідає многочленові G(х)*
, nk молодших розрядів нульові, і відповідно, операція додавання (1) рівносильна приписуванню R(x) до G(x) з боку молодших розряд. Очевидно, що R(х) має зміст контрольних розрядів ЦК. Таким чином, циклічний код можна будувати, приписуючи до кожної комбінації безнадлишкового коду G(х) залишок від ділення G(х)*
на утворюючий поліном Р(х) коду. Захисні можливості ЦК визначаються утворюючим поліномом Р(х), вибір якого має бути підпорядкований кільком правилам: 1. кількість ненульових членів Р(х) має бути не меншою від кодової віддалі d; 2.степінь полінома Р(х) не може бути меншим за nk (бажано, щоб він дорівнював nk); 3. довжина Р(х) має бути мінімальною. ЦК, утворений поліномом P(x)=x + 1, забезпечує кодову віддаль d = 2 і збігається з кодом з захистом за паритетом, забезпечуючи виявлення не лише поодиноких помилок, але і довільної непарної ...